// 字符串
// 常见题型- 找最长公共前缀 - 统一对比
// 常见题型 - 找回文串 - 用中心扩展算法

// 例题 2：
// 给你一个字符串 s，找到 s 中最长的回文子串
//
//        示例 1：
//
//        输入：s = "babad"
//        输出："bab"
//        解释："aba" 同样是符合题意的答案。
//        示例 2：
//
//        输入：s = "cbbd"
//        输出："bb"
//
//
//        提示：
//
//        1 <= s.length <= 1000
//        s 仅由数字和英文字母组成

// 解题思路：
// 先固定中间一个位置/两个位置
// 向左右两边扩展，找最长回文子串

public class LongestPalindrome {
    public String longestPalindrome(String s) {
        int n = s.length();
        char[] sArr = s.toCharArray();
        int pos = 0;
        int len = 0;
        for(int i = 0; i < n; i++){
            int left = i;
            int right = i;
            while(left >= 0 && right < n){
                if(sArr[left] == sArr[right]) {
                    if(len < right - left + 1){
                        len = right - left + 1;
                        pos = left;
                    }
                    left--;
                    right++;
                }else break;
            }
        }
        for(int i = 0; i < n; i++){
            int left = i;
            int right = i + 1;
            while(left >= 0 && right < n){
                if(sArr[left] == sArr[right]){
                    if(len < right - left + 1){
                        len = right - left + 1;
                        pos = left;
                    }
                    left--;
                    right++;
                }else break;
            }
        }
        String ret = s.substring(pos, pos + len);
        return ret;
    }
}
